﻿/*
 Тестовое задание - реализация пирамидальной сортировки с подсчетом
 количества перестановок элементов и затраченного времени.
 Литовко Л.С. 
 apatheiar@mail.ru
*/

var count_permutation = 0; /*Количество перестановок*/

/*
* MakeHeap - преобразует неотсортированную последовательность в пирамиду
* @param array - неотсортированная последовательность
* @param length - длина последовательности
*/
function MakeHeap(array, begin/*, length*/){
	var length = array.length;
	for (var i = begin; /*2*i+1*/ 2 * i - (begin - 1) < length; ++i){
		var left_child_idx = /*2*i+1*/ 2 * i - (begin - 1);
		var right_child_idx = left_child_idx + 1;
		if (array[i] < array[left_child_idx]){
			if (right_child_idx < length && array[i] < array[right_child_idx]){
				var temp_i = array[left_child_idx] > array[right_child_idx] ? left_child_idx : right_child_idx;
				
				Swap(array, i, temp_i);
				++count_permutation;
				i = begin - 1; // сбрасываем счетчик, чтобы переупорядочить пирамиду
			}
			else{
				Swap(array, i, left_child_idx);
				++count_permutation;
				i = begin - 1;
			}
		}
		else
			if (right_child_idx < length && array[i] < array[right_child_idx]){
				Swap(array, i, right_child_idx);
				++count_permutation;
				i = begin - 1;
			}
	}
}

/*
* Swap - меняет местами два элемента массива
* @param array - массив, в котором производиться перестановка
* @param i, j - индексы элементов для перестановки
*/
function Swap(array, i, j){ 
	var temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

/*
* Shift - сдвиг содержимого массива на одну позицию влево
* @param array - массив, который необходимо сдвинуть
* @param i - длина массива
*/
function Shift(array, i){ 
	for (var j = 0; j < i - 1; ++j){
		array[j] = array[j + 1];
	}
}

/*
* HeapSort - пирамидальная сортировка. Функция преобразовывает поданный на 
*            вход массив.
* @param array - массив, который необходимо отсортировать
*/
function HeapSort(array){ 
	var length = array.length;	
	count_permutation = 0;	
	for (var i = 0; length - i  > 0; ++i){
		MakeHeap(array, i/*, array.length*/);
		//alert(array + "\n" + i);
		/*var temp = array[0];
		Shift(array, length - i);
		array[length - i - 1] = temp;
	*/}
}

/*
* Main - основная функция, которая получает пользовательский
*        массив, запускает сортировку и выводит на экран результат работы
*/
function Main(){
	var input_array = document.getElementById('input_array');
	var array_string = input_array.value;		
	array_string = array_string.split(',');
	var array = new Array();	
	for (var i = 0, j = 0; i < array_string.length; ++i){
		var value_of_array = parseInt(array_string[i]);	   
		if (isNaN(value_of_array)){
			alert("Value at position[" + i + "] can't be interpreted as a correct one.\n The value will be skipped.");
		}
		else{
			array[j++] = value_of_array;
		}	    
	}		
	var start = new Date();
	HeapSort(array);
	var end = new Date();
	var work_time = end.getTime() - start.getTime();
	var p1 = document.getElementById('p1').firstChild;
	var p2 = document.getElementById('p2').firstChild;
	var p3 = document.getElementById('p3').firstChild;
	var p4 = document.getElementById('p4').firstChild;
	p1.replaceData(0, p1.length, array);
	p2.replaceData(0, p2.length, array.length);
	p3.replaceData(0, p3.length, work_time);
	p4.replaceData(0, p4.length, count_permutation);
	
}